package com.list;

import com.tgy.util.AbstractList;

import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020-10-22 15:51
 */
public class LinkedList01<E> extends AbstractList<E> {

    private static class Node<E> {

        E element;
        Node<E> next;

        public Node(E element) {

            this.element = element;
        }
    }

    private Node<E> root;

    @Override
    public E get(int index) {

       return nodeOfIndex(index).element;
    }

    @Override
    public E set(int index, E element) {

        checkIndex(index);

        Node<E> node = root;
        for (int i = 0; i <= index; i++) {

            node = node.next;
        }

        node.element = element;
        return element;
    }

    @Override
    public void add(int index, E element) {

        checkAddIndex(index);

        if (index == 0) {

            root = new Node<>(element);
            size++;
            return;
        }

        Node<E> node = root;
        for (int i = 1; i < index; i++) {

            node = node.next;
        }

        Node<E> newNode = new Node<>(element);

        newNode.next = node.next;
        node.next = newNode;

        size++;
    }

    @Override
    public E remove(int index) {
        return null;
    }

    @Override
    public int indexof(E element) {
        return 0;
    }

    @Override
    public void clear() {

    }

    /**
     * 反转链表
     */
    public void reversal() {

        if (size <= 1) {

            return;
        }

//        Node<E> preNode = null,curNode = root, nextNode = null;
//
//        while (Objects.nonNull(curNode)) {
//
//            nextNode = curNode.next;
//            curNode.next = preNode;
//            preNode = curNode;
//            curNode = nextNode;
//        }
//
//        root = preNode;
        reversal(0, size - 1);
    }

    public void reversal(int start, int end) {

        checkIndex(start);

        if (end != -1) {

            checkIndex(end);
        }else {
            end = size - 1;
        }

        if (start >= end) {

            return;
        }


        Node<E> preNode = (end == (size - 1) ? null:nodeOfIndex(end + 1)),
                curNode = nodeOfIndex(start),
                nextNode;

        Node<E> endNode = preNode;
        while (curNode != endNode) {

            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }

        if (start == 0) {

            root = preNode;
        }else {

            nodeOfIndex(start - 1).next = preNode;
        }

    }

    public void recursionReversal(int start, int end) {

        if (size <= 1) {
            return;
        }

        checkIndex(start);

        if (end != -1) {

            checkIndex(end);
        }else {
            end = size - 1;
        }

        if (start >= end) {

            return;
        }

        Node<E> preNode = null,startNode;
        if (start != 0) {

            preNode = nodeOfIndex(start - 1);
            startNode = preNode.next;
        }else {

            startNode = root;
        }

        Node<E> endNode = nodeOfIndex(end);
        Node<E> lastNode = endNode.next;

        doRecursionReversal(startNode,endNode);

        if (start == 0) {

            root = endNode;
        }else {

            preNode.next = endNode;
        }

        startNode.next = lastNode;

    }

    public void stackReversal(int start, int end) {



        if (size <= 1) {
            return;
        }

        checkIndex(start);

        if (end != -1) {

            checkIndex(end);
        }else {
            end = size - 1;
        }

        if (start >= end) {

            return;
        }

        Stack<Node<E>> stack = new Stack<>();

        Node<E> endNode = (end == (size - 1) ? null:nodeOfIndex(end + 1));

        Node<E> preNode = null,node = null;
        if (start != 0) {

            preNode = nodeOfIndex(start - 1);
            node = preNode.next;
        }else {

            node = root;
        }

        while (node != endNode) {

            stack.push(node);
            node = node.next;
        }


        Node<E> stackNode = stack.pop();
        node = stackNode;
        Node<E> beforeNode = null;
        while (!stack.empty()) {

            beforeNode = stack.pop();
            stackNode.next = beforeNode;
            stackNode = beforeNode;
        }

        stackNode.next = endNode;

        if (start == 0) {

            root = node;
        }else {

            preNode.next = node;
        }

    }


    private Node<E> doRecursionReversal(Node<E> node) {


        if (Objects.isNull(node.next)) {
            root = node;
            return node;
        }

        Node<E> doNode = doRecursionReversal(node.next);
        doNode.next = node;
        node.next = null;
        return node;
    }

    private Node<E> doRecursionReversal(Node<E> node,Node<E> endNode) {


        if (node == endNode) {
//            root = node;
            return node;
        }

        Node<E> doNode = doRecursionReversal(node.next,endNode);
        doNode.next = node;
        node.next = null;
        return node;
    }

    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();

        Node<E> node = root;
        for (int i = 0; i < size; i++) {

            if (i != 0) {

                sb.append(",");
            }
            sb.append(node.element);
            node = node.next;
        }

        return sb.toString();
    }

    private Node<E> nodeOfIndex(int index) {

        checkIndex(index);

        Node<E> node = root;
        for (int i = 0; i < index; i++) {

            node = node.next;
        }

        return node;
    }


}
